# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/8/5 19:41 
"""


"""
二叉搜索树(BST）定义
二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：
(1)若左子树不空，则左子树上所有节点的值均小于或等于它的根节点的值；
(2)若右子树不空，则右子树所有节点的值均大于或等于它的根节点的值
(3)左、右子树也分别是二叉搜索树

BST的查询：
若根节点的关键字值等于查找的关键字，返回根节点的值
否则，若小于根节点的关键字值，递归左子树
若大于根节点的关键字值，递归查右子树
若子树不为空，则查找不成功


插入：
与查询类似，判断是左子树，还是右子树，走到叶子节点后直接加一个节点

最值：
最小值：一直往左子树里找
最大值：一直往右子树例找

前驱：
第一个比这个数小的值，
后继：第一个比这个大的值
"""

class Node:
    def __init__(self,data):
        self.data=data
        self.lchild=None
        self.rchild=None


class BST:
    def __init__(self,node_list):
        self.root=Node(node_list[0])
        for data in node_list[1]:
            self.insert(data)

    def search(self,node,parent,data):
        """
        搜索
        Args:
            node:
            parent:
            data:

        Returns:

        """

        if node is None:
            return False,node,parent
        if node.data==data:
            return True,node,parent
        if node.data>data:
            return self.search(node.lchild,node,data)

        else:
            return self.search(node.rchild,node,data)


    def insert(self,data):
        """
        插入
        Args:
            data:

        Returns:

        Note:
                if data in node.data,pass;
                else:
                    data>parent.data,parent node.rchild is Node(data)
                    data<parent.data,parent node.lchild is Node(data)

        """
        flag,n,p=self.search(self.root,self.root,data)
        if not flag:
            new_node=Node(data)
            if data>p.data:
                p.rchild=new_node
            else:
                p.lchild=new_node



    def delete(self,root,data):
        """
        从树中删除data
        Args:
            root:
            data:

        Returns:

        """
        flag,node,p=self.search(self.root,self.root,data)
        #node :表示当前节点
        # p表示父节点
        if not flag:
            print('无该关键字，删除失败！')
        else:
            if node.lchild is None:
                if node==p.lchild:
                    p.lchild=node.rchild
                else:
                    p.rchild=node.rchild
                del p
            elif node.rchild is None:
                if node==p.lchild:
                    p.lchild=node.lchild
                else:
                    p.rchild=node.lchild
                del p
            else:
                #左右子树不为空
                pre=node.rchild
                if pre.lchild is None:
                    node.data=pre.data
                    node.rchild=pre.rchild
                    del pre
                else:
                    next=pre.lchild
                    while next.lchild is not None:
                        pre=next
                        next=next.lchild
                    node.data=next.data
                    pre.lchild=next.rchild
                    del p



